import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 03010570
 * @date 2020/07/09
 * describe:    LeetCode : 面试题 17.13 、恢复空格  https://leetcode-cn.com/problems/re-space-lcci/
 */
public class LeetCode_interview_02_04 {

    public static void main(String[] args) {

    }

    /**
     * 思路1 ：
     * 使用两个 链表 分别存储 小于 x 的节点和大于 x 的节点
     * 使用一个 count 计数 等于 x 的节点；
     * 时间复杂度 ： O(N)
     * 空间复杂度 ： O(N)
     *
     * @param head
     * @param x
     * @return
     */
    public ListNode partition(ListNode head, int x) {
        ListNode smallNode = new ListNode(0);
        ListNode bigNode = new ListNode(0);
        int count = 0;
        ListNode curSmallNode = smallNode;
        ListNode curBigNode = bigNode;
        while (head != null) {
            if (head.val < x) {
                curSmallNode.next = new ListNode(head.val);
                curSmallNode = curSmallNode.next;
            } else if (head.val > x) {
                curBigNode.next = new ListNode(head.val);
                curBigNode = curBigNode.next;
            } else {
                count++;
            }
            head = head.next;
        }
        for (int i = 0; i < count; i++) {
            curBigNode.next = new ListNode(x);
            curBigNode = curBigNode.next;
        }
        curSmallNode.next = bigNode.next;
        return smallNode.next;
    }

}
